1. Field of the Invention
The present invention generally relates to decoding of error-correcting codes, and in particular, to efficient soft-decision decoding of Reed-Solomon and related codes.
The present invention particularly concerns an algorithmic soft-decision decoding procedure for Reed-Solomon codes, the procedure (i) making optimal use of the xe2x80x9csoft-decisionxe2x80x9d reliability information available from a communication or storage system (channel), while (ii) executing in a time that scales polynomially with the length of the code. Said decoding procedure also extends to the decoding of Bose-Chaudhuri-Hocquenghem (BCH) codes and most algebraic-geometry (AG) codes; significantly outperforming the generalized minimum distance (GMD) decoding of Forney, Jr.
2. Description of Prior and Related Art
2.1. Reed-Solomon Codes
Reed-Solomon (RS) codes are among the most extensively used error-correcting codes today, and their practical importance is well established. See the book S. B. Wicker, V. K. Bhargava, Reed-Solomon Codes and Their Applications, IEEE Press, 1994, and in particular the chapters by K. A. S. Immink, Reed-Solomon codes and the compact disc, ibid, 1994; R. J. McEliece, L. Swanson, Reed-Solomon codes and the exploration of the solar system, ibid, 1994; S. B. Wicker, M. Bartz, Reed-Solomon codes in hybrid automatic repeat-request systems, ibid,. 1994; M. B. Pursley, Reed-Solomon codes in frequency-hop communications, ibid, 1994; D. Sarwate, Reed-Solomon codes and the design of sequences for spread-spectrum multiple-access communications, ibid, 1994; and E. R. Berlekamp, G. Seroussi, P. Tong, A hypersystolic Reed-Solomon decoder, ibid, 1994. See also E. R. Berlekamp, R. E. Peile, S. P. Pope, The application of error control to communications, IEEE Commun. Mag., vol. 25, pp. 44-57, 1987; W. W, Wu, D. Haccoun, R. E. Peile, Y. Hirata, Coding for satellite communication, IEEE J. Select. Areas Commun., vol. SAC-5, pp. 724-785, 1987; Consultative Committee for Space Data Systems, Recommendations for Space Data System Standards, Blue Book, 1984; M. B. Pursley, W. E. Stark, Performance of Reed-Solomon coded frequency-hop spread-spectrum communication in partial band interference, IEEE Trans. Commun., vol. COM-33, pp. 767-774, 1985; and D. Divsalar, R. M. Gagliardi, J. H. Yuen, PPM performance for Reed-Solomon decoding over an optical-RF relay link, IEEE Trans. Commun., vol. COM-32, pp. 302-305, 1984.
Reed-Solomon codes are used in digital audio disks (CD""s) and digital versatile disks (DVD""s). See S. B. Wicker, V. K. Bhargava, op. cit. and K. A. S. Immink, op. cit.
Reed-Solomon codes are used in satellite communications. See S. B. Wicker, V. K. Bhargava, op. cit., E. R. Berlekamp, R. E. Peile, S. P. Pope, op. cit., and W. W, Wu, et. al. op. cit.
Reed-Solomon codes are used in deep-space telecommunication systems, including multiple deep-space communication standards. See S. B. Wicker, V. K. Bhargava, op. cit., R. J. McEliece, L. Swanson, op. cit, and Consultative Committee for Space Data Systems, op. cit.
Reed-Solomon codes are used in frequency-hop and spread-spectrum systems. See M. B. Pursley, op. cit., D. Sarwate, op. cit, and M. B. Pursley, W. E. Stark, op. cit.
Reed-Solomon codes are used in error-control systems with feedback. See S. B. Wicker, V. K. Bhargava, op. cit. and S. B. Wicker, M. Bartz, op. cit.
Reed-Solomon codes are used in optical communications. See S. B. Wicker, V. K. Bhargava, op. cit. and D. Divsalar, et. al., op. cit.
2.2 Decoding of Reed-Solomon Codes
The decoding of Reed-Solomon codes is one of the most frequently performed tasks in today""s communication and storage systems. Since the discovery of Reed-Solomon codes in the early 1960""s (see I. S. Reed, G. Solomon, Polynomial codes over certain finite fields, J. Soc. Indust. Appl. Math., vol. 8. pp. 300-304, 1960), a steady stream of work has been directed towards streamlining their decoding algorithms. Today (circa 2000), very efficient techniques are available to accomplish that task. In particular, hard-decision decoders for RS codes have been implemented in hyper-systolic VLSI using algebraic decoding algorithms. Such decoders have been designed to operate at sustained data rates of 820 Mb/s. See E. R. Berlekamp, G. Seroussi, P. Tong, A hypersystolic Reed-Solomon decoder, op. cit.
An important problem in hard-decision decoding of Reed-Solomon codes is that of decoding beyond the error-correction radius (which is equal to one half of the minimum distance of the code). Search techniques have traditionally dominated approaches to this problem. See e.g., R. E. Blahut, Theory and Practice of Error Control Codes, Addison Wesley, 1994. However, for polynomially-bounded decoding complexity, these techniques do not achieve decoding beyond half the minimum distance of the code, in an asymptotic sense.
A breakthrough in this area was achieved by Sudan in 1997. Reference M. Sudan, Decoding of Reed-Solomon codes beyond the error correction bound, J. Compl. vol. 13, pp. 180-193, 1997; and also V. Guruswami, M. Sudan, Improved decoding of Reed-Solomon and algebraic-geometric codes, IEEE Trans. Inform. Theory, vol. 45, pp. 1755-1764, 1999. In the form presented in V. Guruswarni, M. Sudan op. cit., Sudan""s algorithm corrects any fraction of up to xcfx84xe2x89xa61xe2x88x92{square root over (R)} erroneous positions in an RS code of rate R. Thus the error correction capabilities exceed the minimum distance error-correction bound (1xe2x88x92R)/2 for all rates in the interval [0,1]. The present invention makes use of the methods and algorithms developed by V. Guruswami, M. Sudan, op. cit.
2.3 Soft-Decision Decoding
Early in the development of coding theory, it was found convenient to represent communication channels as conveyors of symbols drawn from finite sets. The effects of channel noise were represented by the occasional (random) reception of a symbol other than the one that was transmitted. This abstraction of reality permitted the application of powerful algebraic and combinatoric tools to the code design and decoding problems; Reed-Solomon codes themselves were developed through this abstraction.
In reality, however, channel noise is almost always a continuous phenomenon. What is transmitted may be selected from a discrete set, but what is received comes from a continuum of values. This viewpoint leads to the soft-decision decoder, which accepts a vector of real samples of the noisy channel output and estimates the vector of channel input symbols that was transmitted. Alternatively, a soft-decision decoder can accept any quantization of the real samples of the noisy channel output. By contrast, the hard-decision decoder requires that its input be from the same alphabet as the channel input. It is now well known that soft-decision decoding techniques can provide up to 3 dB more coding gain for the additive white Gaussian channel.
A soft-decision decoder accepts analog values directly from the channel; the demodulator is not forced to decide which of the q possible symbols a given signal is supposed to represent. The decoder is thus able to make decisions based on the quality of a received signal. All of the information on the xe2x80x9cnoisinessxe2x80x9d of a particular received signal is lost when the demodulator assigns a symbol to the signal prior to decoding. It has been estimated that this loss of information results in a 2 to 3 dB loss in performance.
2.4. Soft-decision Decoding of Reed-Solomon Codes
Soft-decision decoding of Reed-Solomon codes is different in many ways from hard-decision decoding. The advantage of soft-decision over hard-decision decoding is adequately established in many works. See, for example, J. G. Proakis, Digital Communications, New York: McGraw-Hill, 1983; C. G. Clark, J. B. Cain, Error Correction Coding for Digital Communication, New York: Plenum, 1981; and U. Cheng, G. K. Huth, Bounds on the bit error probability of a linear cyclic code GF(2i) and its extended code, IEEE Trans. Inform. Theory, vol. 34, pp. 776-735, 1988. This later reference also contains graphs of soft-decision coding gain versus signal-to-noise ratio (SNR) for various RS codes.
The mainstream approach to the problem of soft-decision decoding was pioneered by Forney, and is known as generalized minimum-distance (GMD) decoding. See G. D. Forney, Jr., Generalized minimum distance decoding, IEEE Trans. Inform. Theory, vol. IT-12, pp. 125-131, 1966, and G. D. Forney, Jr., Concatenated Codes, MIT Press, 1966. The complexity of GMD decoding is moderate and ultimately is of the same order as the complexity of hard-decision decoding. See U. Sorger, A new Reed-Solomon decoding algorithm bases on Newton""s interpolation, IEEE Trans. Inform. Theory, vol. IT-39, pp. 358-365, 1993; and also R. Kxc3x6tter, Fast generalized minimum distance decoding of algebraic geometric and Reed-Solomon Codes, IEEE Trans. Inform. Theory, vol. 42, pp. 721-738, 1996. However, the gains that can be realized by GMD decoding are also moderate.
Even though the decoder can often be supplied with reliable soft-decision data relatively easily, the high complexity of optimal soft decoding makes utilization of such data prohibitive. In fact, all the available optimal soft decoding algorithmsxe2x80x94e.g. the algorithm of Vardy and Be""ery (see A. Vardy, Y. Be""ery, Bit-level soft decision decoding of Reed-Solomon codes, IEEE Trans. Communications, vol. 39, pp. 440-445, March 1991) or its extensions (see e.g. V. Ponnampalam, B. S. Vucetic, Soft decision decoding of RS codes, in Proc. 13th AAECC Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Hawaii, USA, November 1999; S. Ray-Chaudhuri, A. H. Chan, Bit-level parallel decoding of Reed-Solomon codes, in Proc. 31st Allerton Conference on Communications, Control and Computing, Monticello, Ill., September, 1993)xe2x80x94run in time that scales exponentially with the length of the code. This makes the use of such algorithms generally infeasible in practice.
In this context, the reference of E. R. Berlekamp et. al., op. cit., states that xe2x80x9cthe major drawback with RS codes for satellite use is that the present generation of decoders do not make full use of bit-based soft-decision information.xe2x80x9d In the same context, the reference of S. B. Wicker, V. K. Bhargava. op. cit., states that xe2x80x9cthe xe2x80x98Holy Grailxe2x80x99 of Reed-Solomon decoding research is the maximum-likelihood soft-decision decoder.xe2x80x9d Thus, due to the ubiquity of RS codes in today""s communication and recording systems, efficient soft decoding of RS codes, while making full use of the soft-decision reliability data, remains one of the most important tasks of coding theory and practice.
The present invention will be seen to concern a soft-decision Reed-Solomon decoding method and decoder that (i) makes full use of soft decision information and (ii) runs in time that scales polynomially with the length of the code. The soft-decision decoding method and decoder of the present invention will be also seen to be effective in operating on hard-decision input data.
This invention provides a method for soft-decision decoding of error correction codes such as Reed-Solomon, BCH, and, in general, algebraic-geometric codes. Analog samples that have been received from a communication channel are processed to estimate the likelihoods of the symbols that were input to the communication channel. In accordance with one embodiment of the invention, reliability information concerning the relative likelihoods of different symbols is converted into a set of algebraic interpolation conditions. The interpolation conditions are used to produce a polynomial which, when factored, will yield factors that correspond to codewords. In accordance with a further embodiment of the invention, a vector of symbols received from the communication channel is used to compute a set of algebraic interpolation conditions. The computed set of algebraic interpolation conditions is interpolated to find an interpolation polynomial that satisfies the algebraic interpolation conditions. The interpolation polynomial is then factored to find factors that correspond to codewords of the error correcting code. In this manner, a list of candidate codewords is generated.
It is a primary object of the present invention to provide an efficient algorithmic method for soft-decision decoding of Reed-Solomon codes and related error-correcting codes.
More particularly, it is a primary object of the present invention to provide an algorithm that always runs in time that scales polynomially with the length of the code, while significantly outperforming (i) conventional hard-decision decoding, (ii) decoding beyond half the minimum distance, as taught by Guruswami and Sudan op. cit., and (iii) GMD soft-decision decoding. Specifically, the algorithmic method of the present invention provides substantially more coding gain than any of the above methods.
Reference is now made to FIG. 2, which should be considered exemplary only and not delimiting of the scope of the present invention. FIG. 2 is a graph showing a comparison of the performance of the method of the present invention for a simple concatenated Reed-Solomon coding scheme. An RS(256,144,113) code of length 256 and dimension 144 over a finite field with 256 elements is concatenated with a binary parity check code of length 9, so that the overall coding scheme represents a binary code of rate 1/2. The channel is an additive, white, Gaussian noise (AWGN) channel. The inner parity check code is in all cases decoded with a maximum a posteriori likelihood decoding algorithm. The four different curves of FIG. 2 correspond to the performance achieved by two hard-decision decoding algorithms and two soft-decision decoding algorithms. The two hard-decision decoding algorithms are (i) conventional Berlekamp-Welch 40 decoding up to half the minimum distance, and (ii) the algorithm by Guruswami and Sudan 41 that decodes beyond half the minimum distance. The two soft-decision decoding algorithms are (iii) Forney""s GMD decoding 42 and (iv) the algebraic soft-decision decoding algorithm 43 of the present invention taught within this specification. It can be seen from FIG. 2 that the algorithmic method of the present invention significantly outperforms the other methods.
It is a related object of the present invention that the efficient, algorithmic method for the soft-decision decoding of Reed-Solomon codes should have additional useful features. Among the most useful features of the algorithmic method of the present invention is that there exists a trade-off between complexity and performance and, moreover, this trade-off can be chosen freely in real-time by adjusting a single parameter in the decoding procedure. Hence, the coding gain provided by the Reed-Solomon code can be traded for computational complexity in real-time. This is true in any application. For any desired level of performance, the complexity is bounded by a polynomial in the length of the code. In particular, the computational complexity can be adjusted to any required performance within a fundamental bound. (This bound is described in detail in Appendix A to this application.)
In still yet another object of the present invention that the efficient, algorithmic method of soft-decision decoding of Reed-Solomon codes should readily extend to the decoding of Bose-Chaudhuri-Hocquenghem codes (BCH) and most algebraic-geometry (AG) codes.
Briefly, to achieve the objects of the present invention, an algorithmic decoding method consisting of three major steps is disclosed. For much later reference, let q={xcex11,xcex12, . . . , xcex1q} denote a finite field with q elements, where q is a nonnegative integer power of a prime integer. Given that a codeword c=(c1,c2, . . . , cn) of a Reed-Solomon code over the alphabet q={xcex11,xcex12, . . . , xcex1q} is transmitted over a channel, and a vector y=(y1,y2, . . . , yn) is observed at the channel output, the input to the algorithm consists of the qxc3x97n soft-decision reliability matrix Π whose entries are
xcfx80i,j=Pr(cj=xcex1i|yj)
where Pr(cj=xcex1i|yj) is the probability that the j-th transmitted symbol was xcex1i given that the j-th observed symbol yj. The three major steps of the algorithmic method are as follows:
1. Determination of Interpolation Points: Given the reliability matrix Π, compute the multiplicity matrix M which determines the interpolation points and their multiplicities.
2. Soft Interpolation: Given the multiplicity matrix M from the previous step, find the non-trivial polynomial QM(X,Y) of the lowest (weighted) degree whose zeros and their multiplicities are as specified by the matrix M.
3. Factorization Step: Given the non-trivial polynomial QM(X,Y) from the previous step, find all factors of QM(X,Y) of type Yxe2x88x92ƒ(X), where ƒ(X) is a polynomial in X whose degree is less than the dimension k of the Reed-Solomon code. Given the polynomials ƒ(X), reconstruct from each of them a codeword of the RS code.
These three steps can be performed either sequentially or in a pipeline. The overall output of the algorithmic method are the codewords resulting from the factorization step. Each of the three steps may be realized and obtained as described below and in the detailed specification.
It should first be understood as background to understanding the present invention that the word xe2x80x9csoftxe2x80x9d occurring in the phrase xe2x80x9csoft-decision decoding of Reed-Solomon codesxe2x80x9d means something other, and different, than the more common, and older, hard-decision decoding of Reed-Solomon codes. As explained in the Background section of this specification, a soft-decision decoder accepts a vector of real samples of a noisy channel output, which samples correspond to the reliabilities of possible input symbols, and estimates the vector of channel input symbols that was transmitted.
There is but little prior art of direct relevance to the present invention being that soft decoding is considerably different from, and advanced over, standard (xe2x80x9chardxe2x80x9d) Reed-Solomon decoding. All previous art regarding standard hard-decision RS decoding is somewhat distant from the present invention. On the other hand, the prior art of direct relevance to the present invention is relatively new: The method of the present invention builds on, and significantly extends upon, an algebraic interpolation algorithm proposed recently by V. Guruswami, M. Sudan op. cit. (for hard-decision decoding).
Accordingly, in one of its aspects the present invention will be recognized to be embodied in a method of decoding an error-correction code wherein the method is algebraic, i.e., algebraic soft-decision decoding. In the context of this invention, algebraic soft-decision decoding may be understood as a decoding method that proceeds by converting reliability information concerning the relative likelihoods of different symbols into a set of algebraic interpolation conditions. A set of algebraic interpolation conditions may be understood, for example, as a system of equations over a finite field. Although soft-decision decoding of various codes has previously been performed (see E. R. Berlekamp, Soft Decision Reed-Solomon Decoder, U.S. Pat. No. 4,821,268, issued Apr. 11, 1989; E. R. Berlekamp, Bounded distance+1 soft-decision Reed-Solomon decoding, IEEE Trans. Inform. Theory, vol. 42, pp. 704-721, 1996; N. Kamiya, A sufficient condition for a generalized minimum distance, Reed-Solomon decoder to ensure correct decoding, IEICE Transactions Fundamentals, vol. E80-A, pp. 2073-2088, 1997; M. S. Oh, P. Sweeney, Bit-level soft-decision sequential decoding for Reed Solomon codes, Workshop on Coding and Cryptography, Paris, France, January 1999; V. Ponnampalam, B. S. Vucetic, Soft decision decoding of Reed-Solomon codes, in Proc. 13th Symp. Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes, Honolulu, Hi., USA, November 1999; S. Ray-Chaudhuri, A. H. Chan, Bit-level parallel decoding of Reed-Solomon codes, in Proc. 31st Allerton Conference on Communications, Control and Computing, Monticello, Ill., September 1993; S. K. Shin, P. Sweeney, Soft decision decoding of Reed-Solomon codes using trellis methods, IEE Proc.-Commun., vol. 141, pp. 303-308, 1994; S. K. Shin, P. Sweeney, Evaluation of efficient trellis methods for soft decision decoding of Reed-Solomon codes, IEE Proc.-Commun., 1996, vol. 143, pp. 61-67, 1996; D. J. Taipale, M. J. Seo, An efficient soft-decision Reed-Solomon decoding algorithm, IEEE Trans. Inform. Theory, vol. 40, pp. 1130-1132, 1994; A. Vardy, Y. Be""ery, Bit-level soft-decision decoding of Reed-Solomon codes, IEEE Trans. Commun., vol. 39, pp. 440-445, 1991), it has never been algebraically so performed, as was previously discussed. The error-correction code to be decoded may in particular be a code of the Reed-Solomon, BCH, or algebraic-geometry types.
Alternatively, the present invention may be considered to be embodied in a method of decoding an error-correction code that is characterized by transpiring in polynomial time. Again, and although optimal soft-decision decoding has previously been performed, it has never heretofore been so performed in polynomial time, again as was previously discussed. The code may again, in particular, be a code of the Reed-Solomon, BCH, or algebraic-geometry types.
In greater detail, in the preferred embodiment of the present invention a qxc3x97n reliability matrix Π with elements xcfx80i,j is received upon a communications channel. The alphabet is of size q, and n is the length of the Reed-Solomon code.
The preferred algebraic soft-decision decoding method, in accordance with the present invention, then consists of (i) computing a multiplicity matrix M, (ii) interpolating so as to find a non-trivial polynomial which passes through the points specified by M, (iii) factorizing the non-trivial polynomial into factors that correspond to codewords, and (iv) selecting a single codeword from among these factors.
Namely, (i) a multiplicity matrix M is found that has non-negative integer entries mi,j corresponding to the received reliability matrix Π, which entries mi,j specify interpolation points.
Then, given this multiplicity matrix M, (ii) interpolating is performed so as to find a non-trivial polynomial QM(X,Y) of lowest (1,kxe2x88x921)-weighted degree such that QM(X,Y) has a zero of multiplicity at least mi,j in the point (xj,xcex1i).
Then, given this non-trivial polynomial QM(X,Y), (iii) the polynomial is factored so as to find factors of type Yxe2x88x92ƒ(X), deg(ƒ) less than k, which factors correspond to codewords.
Then, given these codewords, (iv) a single codeword, most suitable to reconstitute from the received reliability matrix Π the data that was originally transmitted upon the communications channel, is selected.
In still greater detail, the (i) finding the multiplicity matrix M preferably transpires by a process of:
1) commencing with an initial reliability matrix Π*=Π as received, and with an empty all-zero matrix M into which the interpolation points will be recorded, and with an integer s representing the total number of interpolation points,
2) finding a position (i,j) of the largest element in Π*,
3) deriving xcfx80*i,j←xcfx80i,j/(mi,j+2); mi,j←mi,j+1; and s←sxe2x88x921
4) deciding if s=0, and if so then outputting M, else returning to performing the 2) finding and the 3) deriving and the 4) deciding.
The algorithmic method of the present invention will be taught, and proved, within this specification disclosure in the formal language of mathematics, which language of mathematics also serves to rigorously define the invention. However, and at the risk of oversimplification, it is possible to illustrate, by way of a simple example, one of the main components of the present invention, thereby according insight into how the invention works.
An example of the present invention that substantially illustrates the main idea behind the determination of interpolation points (which example is later again set forth in Section 2 of the Description of the Preffered Embodiment part of this specification disclosure, although at that point almost exlusively in mathematical language) is as follows.
Suppose there are five positions in an exemplary set, and each position can take five possible values i.e., {1, 2, 3, 4}. Suppose a codeword c=(1, 2, 3, 4, 0) is sent. For later reference, we make note now, in passing, that this particular sent codeword c has a very easy, and straightforward, relationship to its positions: namely, if a position i of the sent codeword c is represented as xi, and the value of that position i represented as yi, then y1=xi+1 modulo 5. Similarly, any sent codeword can be represented as a polynomial expression. Mathematically, this is expressed as:
5(5,2)={(ƒ(0), ƒ(1), ƒ(2), ƒ(3), ƒ(4)):=ƒ(X)a+bX, a,b∈5}
where 5(5,2) is Reed-Solomon code of length 5 and dimension 2 over the field 5=5. Accordingly, there are qk=52=25 codewords, corresponding to 25 different polynomials, as shown in the following table:
Now, assume that the sent the sent codeword is received as a vector y such that the 5xc3x975 matrix Π with elements xcfx80i,j=Pr(cjxe2x89xa1i|yj) reads:
This matrix Π is called the reliability matrix; it shows the probability that a code symbol of a particular value was received at each position of the code. The reliability matrix can be computed from the receive vector y using the method taught in Section 2 of the Description of the Preferred Embodiment part of this specification.
Although some positions of the exemplary reliability matrix Π show a high probability that some one particular code value was indeed received in a particular position (with correspondingly low probabilities that any other value should have been received in that position), other positions of the same matrix show only but low confidence in the value of the received symbol. For example, the 0.9900 probability value at position (2,1) of the reliability matrix Π indicates a very high probability that the value 2, and no other, was received at position 1. Conversely, the 0.40 probability value at position (3,4) of the reliability matrix Π indicates only but slight confidence that the value 3, and no other, was received at position 4.
In classic Reed-Solomon xe2x80x9chardxe2x80x9d decoding, a decision is derived from each column of the reliability matrix Π. Interpreting the maximum value in each of the five columns, as explained above, the sent codeword c is interpreted to be (4,2,3,3,3). This represents three errors (out of five positions) relative to the codeword (1,2,3,4,0) that was actually sent. The communications channel upon which the codeword c was sent is apparently very noisy.
However, the present invention will show how the codeword actually sent may be fully accurately recovered in this example. First, the reliability matrix Π contains a great deal of information. Given the information in Π, it is clear that we would like to weigh each position differently. This can be done by requiring that a polynomial QM(X,Y) should pass through different points with different multiplicities. This is akin to finding the equation of a curve that passes through given discrete points on a plane. If the equation of such a curve can be found, then it contains information regarding all the points.
As discussed above, the three major steps of the algorithm, in accordance with the present invention, to recover the codeword are: 1) Determination of Interpolation Points, 2) Soft Interpolation, and 3) Factorization Step. The first step (1) Determination of Interpolation Points is now illustrated by example.
The determination consists of computing entries in the multiplicity matrix M by an iterative and recursive process. Mathematically the process commences with (i) an initial reliability matrix Π*=Π as received from a communications channel, (ii) an empty all-zero matrix M into which the entries will be recorded, and (iii) an integer s representing the total number of interpolation points.
Next, a position (i,j) of the largest element in Π* is found. Next, each of
(i) xcfx80*i,j←xcfx80i,j/(mi,j+2); (ii) mi,j←mi,j+1; and (iii) s←sxe2x88x921,
are derived. Finally, it is decided if s=0, and if so then M is outputted, else return is made to performing the finding and the deriving and the deciding.
An easy way to understand what this means is by example. Let s, or the number of iterations to be made, equal 7. This number s is arbitrary: it will later be discussed that the number of iterations in the algorithm of the present invention may be traded-off for accuracy in the recovery of RS codewords. It will later be found that, for the noise experienced on this channel in the example that follows, 7 iterations will suffice for accurate codeword recovery. More iterations could be performed, but are unnecessary.
The initial, empty and all zero matrix M is:                     xe2x80x83                            xe2x80x83                    M                      xe2x80x83                            xe2x80x83                        0              0              0              0              0                  0              0              0              0              0                  0              0              0              0              0                  0              0              0              0              0                  0              0              0              0              0      
Displaying this matrix M, and the initial exemplary reliability matrix Π*=Π together we have:
Now, by the process of the present invention, (i) the single largest numerical probability in the matrix Π* is located, (ii) the corresponding position of the matrix M is augmented by +1, and (iii) this single largest probability in the matrix Π is divided by the augmented value +1 (or in this case, by the number 2) and replaced in the matrix Π*. For matrix M, and matrix Π*, we then get the following (changed positions are shown in boldface for convenience of reference):
The process continues: locate the now-highest probability in the matrix Π*, and adjust it and the corresponding position of the matrix M. Thus the next, second, iteration produces:
Likewise, the third iteration produces:
Consider that in the fourth iteration the division of the original probability xcfx802,2 is now by 3, and no longer by 2:
Doubtless by now, the mathematical expression of this process, which is given above, will be better understood. The process continues:
Eventually, the iteration count s having decreased to zero, the iterative process terminates. The final reliability matrix M, given immediately above, can alternatively be expressed as:
Importantly to understanding the scope of the present invention, from this point forward, certain mathematical processes employed are substantially conventional. Namely, using conventional interpolation methods, the final multiplicity matrix M is interpreted so as to find a non-trivial polynomial QM(X,Y) of lowest (1,kxe2x88x921)-weighted degree such that QM(X,Y) has a zero of multiplicity at least mi,j at the point (xcex1i,xj).
For the derived multiplicity matrix M above, this polynomial QM(X,Y) turns out to be:
QM(X,Y)=1+X+Yxe2x88x92X2xe2x88x92Y2xe2x88x922X2Y+Y2Xxe2x88x92Y3+X4xe2x88x922YX3xe2x88x92X2Y2+2Y3X.
Continuing, this polynomial is factorized into factors of type Yxe2x88x92ƒ(X), where deg(ƒ) less than k. This factoring, while non-trivial, is mathematically well understood and is, for example, taught in the prior art reference of Guruswami and Sudan, op. cit.
In accordance with the present invention, these factors correspond to potential codewords. Given these potential codewords, a single new codewordxe2x80x94suitable to reconstitute from the received reliability matrix Π the data that was originally transmitted upon the communications channelxe2x80x94is selected. Continuing with the example, the derived polynomial QM(X,Y) factors as:
QM(X,Y)=(Yxe2x88x92Xxe2x88x921)(Y+1+2X)(Y+1+3XY+3X+3X2).
We identify the two solutions (Yxe2x88x92Xxe2x88x921) and (Y+1+2X) as corresponding to tentative codewords. Of these two solutions, the solution (Yxe2x88x92Xxe2x88x921), or, equivalently, Y=X+1, corresponds to the sent codeword. It may now be recalled that y=x+1 was indeed the relationship between the bit positions xi and yi of the sent codeword c.
The mathematical process of the present invention has thus sufficed to precisely recover the Reed-Solomon codeword transmitted upon a channel. This has efficiently transpired, in polynomial time, nonetheless that the channel is so noisy that less than half, or forty percent (40%), of the codeword was received correctly.
As a more restrictive characterization of the present invention, the invention will be recognized to be embodied in method of soft-decision decoding a forward error-correction code of the Reed-Solomon, BCH, or algebraic-geometry types, wherein the method is both (i) algebraic, and (ii) transpiring in polynomial time.
The decoding method is characterized in that the magnitude of a coding gain provided by the Reed-Solomon code can be traded-off for computational complexity; relatively more coding gain being realized at relatively more computational complexity while relatively less coding gain is realized at relatively less computational complexity. In this method, the computational complexity is always bounded by a polynomial function of the length of a codeword of the Reed-Solomon code.
If this method of decoding a Reed-Solomon code (or a BCH subfield subcode of the Reed-Solomon code) is applied on a q-ary symmetric communication channel then, as the number of interpolation points becomes very large, it will produce a list of candidate codewords containing the particular codeword at the input to the q-ary symmetric communications channel, provided that less than t errors have occurred, further provided that xcfx84=t/n satisfies the inequality                     (                  1          -          τ                )            2        +                  τ        2                    q        -        1               greater than   R
where q is the number of symbols of the symmetric communication channel, and R is the rate of the Reed-Solomon code.
Similarly, if this method of decoding of a Reed-Solomon code (or a BCH subfield subcode of the Reed-Solomon code) is applied on a q-ary symmetric erasure communication channel then, as the number of interpolation points becomes very large, it will produce a list of candidate codewords containing the particular codeword at the input to the q-ary symmetric erasure communication channel, provided that less than t errors have occurred, further provided that the fraction xcfx84=t/n satisfies the inequality:                     1                  1          -          σ                    ⁢              (                                            (                              1                -                τ                -                σ                            )                        2                    +                                    τ              2                                      q              -              1                                      )              +          σ      q        ≥  R
where q is the number of symbols of the q-ary symmetric erasure communication channel, not counting the symbol xcfx86 denoting erasure, "sgr" is the number of erasures that occurred, and R is the rate of the Reed-Solomon code.
Similarly, if this method of decoding a Reed-Solomon code (or a BCH subfield subcode of the Reed-Solomon code) is applied on a q-PSK communication channel then, as the number of interpolation points becomes very large, it will produce a list of candidate codewords containing the particular codeword at the input to the q-PSK channel, provided that less than s errors to the nearest neighbors and less than t errors beyond the nearest neighbors have occurred, further provided that the fractions "sgr"=s/n and xcfx84=t/n satisfy the inequality:                     (                  1          -          τ          -          σ                )            2        +                  τ        2                    q        -        3              +                  σ        2            2        ≥  R
where q is the number of symbols of the q-PSK communication channel and R is the rate of the Reed-Solomon code.
Accordingly, in one of its aspects, the present invention may be considered to be embodied in a method of decoding an error-correcting code. The error-correcting code has a number of codewords, with each codeword having multiple symbols. The error-correcting code is of the Reed-Solomon type and/or of the Bose-Chaudhuri-Hocquenghem (BCH) type.
The decoding method constitutes algebraic soft-decision decoding by act of converting reliability information concerning the relative likelihoods of the different code symbols into algebraic interpolation conditions. Ergo, by its reliance on the xe2x80x9csoftxe2x80x9d reliability information, the method is called a soft-decision decoding method.
In accordance with the present invention, data inputs to the algebraic soft-decision decoding method commonly include reliability information concerning the relative likelihoods of different code symbols and/or data from which the reliability information concerning the relative likelihoods of different code symbols can be computed. With these inputs, the algebraic soft-decision decoding consists essentially of three steps.
First, given the reliability information, computing from this reliability information a set of algebraic interpolation conditions.
Next, given the computed algebraic interpolation conditions, interpolating to find a non-trivial interpolation polynomial that satisfies these conditions.
Then, given the interpolation polynomial, factoring the polynomial to find factors that correspond to codewords of the Reed-Solomon code or the BCH code, therein generating a list of candidate codewords.
In more formal, mathematical terms, the algebraic soft-decision decoding method may be considered to be applied to an (n,k,d) Reed-Solomon code over a finite field q with q elements, or, equivalently (for the operation of the present invention) and alternatively, an (n,kxe2x80x2,dxe2x80x2) BCH code over a finite field qxe2x80x2 with qxe2x80x2 elements. In these expressions nxe2x89xa71 is the length, kxe2x89xa6n is the dimension, and d=nxe2x88x92k+1 is the minimum distance of the Reed-Solomon code, while n is the length, kxe2x80x2xe2x89xa6k is the dimension, and dxe2x80x2xe2x89xa7d is the minimum distance of the BCH code, the BCH code being but a subfield subcode of the Reed-Solomon code. For each of the n code symbols of the Reed-Solomon code, the input to the method of the present invention includes reliability information concerning the relative likelihood of each code symbol being equal to a xcex1∈q for each element xcex1 of the finite field q, and/or data from which such reliability information can be computed.
With these inputs, the three steps of the algebraic soft-decision decoding method are as follows:
First, given the reliability information, non-negative integer-valued numbers mi,j are computed for each position j in the code, where 1xe2x89xa6jxe2x89xa6n, and for each element xcex1i∈q, where 1xe2x89xa6ixe2x89xa6q, so that the total number of non-zeros among the non-negative integer-valued numbers mi,j depends on the reliability information.
Second, given these numbers mi,j, a (non-trivial) polynomial QM(X,Y) is found by interpolating, so that QM(X,Y) has a zero of multiplicity at least mi,j at the point (xj,xcex1i) for each j in the range 1xe2x89xa6jxe2x89xa6n and each i in the range 1xe2x89xa6ixe2x89xa6q, this polynomial QM(X,Y) best having the least possible (1,kxe2x88x921)-weighted degree. (By xe2x80x9cbest havingxe2x80x9d it is meant only that the method works faster to produce better results when the polynomial QM(X,Y) so has the least possible (1,kxe2x88x921)-weighted degree; the method will still work even if the polynomial QM(X,Y) does not so have the least possible (1,kxe2x88x921)-weighted degree.)
Third, given the polynomial QM(X,Y), this polynomial is factored to find factors of type Yxe2x88x92ƒ(X), where the degree of the polynomial ƒ(X) is less than k, each factor corresponding to a codeword of the Reed-Solomon code or the BCH code, thereby generating a list of candidate codewords.
In the preferred methods, each of the computing and the interpolating and the factoring have a computational complexity that is always bounded by a polynomial function of the length n of the Reed-Solomon code and/or the BCH code. Accordingly, the entire algebraic soft-decision decoding has a computational complexity that is always bounded by a polynomial function of the length n of the Reed-Solomon code and/or the BCH code.
Any of the computing, the interpolating, and the factoring may be implemented in special purpose digital logic, including digital signal processing (DSP), circuits, and/or by software in a general purpose digital computer.
The method of the present invention is most often used in concatenated coding schemes, multilevel coding schemes, and combinations thereof. It may be, for example, used in a communication system, in a recording system, or in multitudinous other systems in which error-correcting codes are employed.
In another of its aspects, the present invention may be considered to be embodied in a method of decoding a Reed-Solomon error-correcting code of length n and rate R over a finite field q with q elements, or, equivalently, a Bose-Chaudhuri-Hocquenghem (BCH) error-correcting code of length n and rate Rxe2x80x2 over the finite field q, on a channel of type drawn from the group consisting of q-ary symmetric channels, q-ary symmetric erasure channels, and q-PSK channels.
In such an environment, the input to the method comprises data that includes a vector y=(y1,y2, . . . , yn) observed at the channel output, where all the n elements of the vector y belong to the finite field q in the case of q-ary symmetric channels and q-PSK channels, but, in the case of q-ary symmetric erasure channels, all the n elements of the vector y belong to q∪xcfx86, the special symbol xcfx86 denoting erasure.
The method essentially consists of three steps.
First, given the vector y=(y1,y2, . . . , yn), from this vector y a set of algebraic interpolation conditions is computed.
Second, the computed set of algebraic interpolation conditions is interpolated to find a (non-trivial) interpolation polynomial that satisfies the algebraic interpolation conditions.
Third, given the interpolation polynomial, this polynomial is factored to find factors that correspond to codewords of the Reed-Solomon code or the BCH code. Thus a list of candidate codewords is generated.
Each of the computing, the interpolating and the factoring has computational complexity that is always bounded by a polynomial function of the length of the Reed-Solomon code and/or the BCH code.
The present invention may be thus characterized by its application to Reed-Solomon error-correcting codes, to BCH error-correcting codes, and to algebraic-geometric codes in general. Notably, the present invention can be also applied to the output of a hard-decision channel. Since no probability accompanies the output of a hard-decision channel, the substantial power of the soft-decision decoding of the present invention is wasted, but the present invention will still operate to decode RS, BCH, and algebraic-geometric error-correcting codes, while outperforming all the existing hard-decision decoding methods.
The present invention is thus better defined by what it does than exactly (i) what it operates on, as inputs, and, indeed, (ii) what it produces, as output. In illustration of (ii), the output can be considered to be the list of candidate codewords, or, by selection in a fourth step, some subset of these codewords (which may include a subset of one, meaning one codeword). In all cases, the essence of the present invention is that it is converting reliability information concerning the relative likelihoods of the different code symbols into algebraic interpolation conditions, and then proceeding to produce from the interpolation conditions a polynomial which, when factored, will deliver up factors that correspond to codewords. Ergo, the soft-decision decoding of the present invention uses reliability informationxe2x80x94commonly heretofore discardedxe2x80x94to decode Reed-Solomon, BCH, and algebraic-geometric codes.
In still yet another of its aspects, the present invention may be used in a concatenated coding scheme, wherein a maximum a posteriori likelihood (MAP) algorithm, such as the BCJR decoding algorithm (see L. R. Bahl, J. Cocke, F. Jelinek, J. Raviv, Optimal decoding of linear codes for minimizing symbol error rate, En; Trans. Inform. Theory, vol. 20, pp. 284-287, 1974), is preferably employed to decode the inner code(s). The present invention may be also used in a multilevel coding scheme, or in a coding scheme that combines multilevel coding with concatenated coding.
The method of the present invention may be implemented in either software or hardware or any combination thereof. In particular, any one of the computation (determination of interpolation points), interpolation, and factorization steps of the decoding method may be implemented in either special purpose digital logic or by software in a general purpose digital computer.
The present invention may be used in a communication system, such as a cable-modem, an ISDN line, a satellite telecommunications link, a wireless communications (multi-user) system, and many others. The present invention may be also used in a recording system, such as a magnetic disk (read and write channels), a magnetic tape, a compact disk, a DVD, as well as other magnetic, optical, and holographic storage media.
The following illustrates a possible implementation of the present invention in a communication system 20. The communication system has a source of a data 22, a Reed-Solomon encoder 23 of the data producing a Reed-Solomon codeword, and a decoder 24, as illustrated in FIG. 1.
The decoder includes (1) a re-encoder 26 receiving the reliability matrix Π and producing an estimated received Reed-Solomon codeword, the re-encoder supplying this Reed-Solomon codeword to each of (2) an interpolator 28, also receiving chosen interpolation points from an interpolation point chooser 30 to produce a function QM(X,Y), (3) a factorizer 32 also receiving the function QM(X,Y) from the interpolator to produce a list of candidate Reed-Solomon codewords, (4) an interpolation point chooser operating with the reliability matrix Π, and (5) a selector 34, also receiving the candidate codewords from the factorizer, for selecting a subset of codewords as does best permit the reconstituting of the sent data from the received matrix Π.
The (4) interpolation point chooser records points in the multiplicity matrix M by process ofxe2x80x94as was stated beforexe2x80x94(1) commencing with an initial reliability matrix Π*=Π as received, and with an empty all-zero matrix M into which the points will be recorded, and with an integer s representing the number of interpolation points, (2) finding a position (i,j) of the largest element in Π*, (3) deriving xcfx80*i,j←xcfx80i,j/(mi,j+2); mi,j←mi,j+1; and s←sxe2x88x921, and (4) deciding if s=0, and if so then outputting M, else returning to performing the (2) finding and the (3) deriving and the (4) deciding.
These and other aspects and attributes of the present invention will become increasingly clear upon reference to the following drawings and accompanying specification.